package com.exam.microsoft;


import java.util.PriorityQueue;

/**
 * date:
 * description:
 */
public class Solution001 {
    public static void main(String[] args) {
        int[] nums = {5, 19, 8, 1};
        Solution001 instance = new Solution001();
        int res = instance.solution(nums);
        System.out.println(res);
    }

    public int solution(int[] A) {
        int res = 0;
        int len = A.length;
        int total = 0;
        PriorityQueue<Double> maxHeap = new PriorityQueue<>(len, (x1, x2) -> {
            if(x1 < x2){
                return 1;
            } else if(x1 > x2) {
                return -1;
            } else {
                return 0;
            }
        });
        for (int i = 0; i < len; i++) {
            maxHeap.offer((double) A[i]);
            total += A[i];
        }
        double target = total / 2.0;
        while(target > 0) {
            double maxNum = maxHeap.poll();
            target -= maxNum / 2.0;
            maxHeap.offer(maxNum / 2.0);
            res++;
        }
        return res;
        // write your code in Java 8 (Java SE 8)
    }
}
